package dtst;

import java.util.*;

public class Hot100 {

    // 螺旋矩阵
    public List<Integer> spiralOrder(int[][] matrix) {
        int[][] DIRT = new int[][]{{0,1},{1,0},{0,-1},{-1,0}};
        int m = matrix.length;
        int n = matrix[0].length;
        int size = m*n;
        // 从(0,-1)开始
        int i=0;
        int j=-1;
        List<Integer> ret = new ArrayList<>(size);
        for(int di=0;ret.size()<size;di=(di+1)%4){
            for (int k=0;k<n;k++){
                i += DIRT[di][0];
                j += DIRT[di][1];
                ret.add(matrix[i][j]);
            }
            int tmp = n;
            n = m-1;
            m = tmp;
        }
        return ret;
    }

    // 最长无重复字符子串
    public int lengthOfLongestSubstring(String _s) {
        char[] s = _s.toCharArray();
        int[] hash = new int[128];
        int n = s.length;
        int ret = 0;
        for(int right=0;right<n;right++){
            hash[s[right]]++;
            int left = right-n+1;
            if(left<0) continue;
            while (hash[s[right]]>1){
                hash[s[left++]]--;
            }
        }
        return ret;
    }

    // 找到字符串中所有的字母异位词
    public List<Integer> findAnagrams(String _s, String p){
        int[] hashS = new int[128];
        int[] hashP = new int[128];
        List<Integer> ret = new ArrayList<>();
        for(char ch:p.toCharArray()){
            hashP[ch]++;
        }

        char[] s = _s.toCharArray();

        for (int right=0;right<s.length;right++){
            hashS[s[right]]++;
            int left = right-p.length()+1;
            if (left<0) continue;
            if (Arrays.equals(hashP,hashS)){
                ret.add(left);
            }
            hashS[s[left]]--;
        }
        return ret;
    }

    // 接雨水
    public int trap(int[] height){
        int n = height.length;
        int[] left = new int[n];
        int[] right = new int[n];
        left[0] = height[0];
        right[n-1] = height[n-1];
        for (int i=1;i<n;i++){
            left[i] = Math.max(left[i-1],height[i]);
        }

        for (int i=n-2;i>0;i--){
            right[i] = Math.max(right[i+1],height[i]);
        }

        int ret = 0;
        for (int i=1;i<n-1;i++){
            ret+=Math.min(left[i],right[i])-height[i];
        }
        return ret;

    }

//    // 全排列
//    private List<List<Integer>> muteRet = new ArrayList<>();
//    private boolean[] vis;
//    private int mutesize;
//    private List<Integer> mutePath = new ArrayList<>();
//    public List<List<Integer>> permute(int[] nums) {
//        mutesize = nums.length;
//        vis = new boolean[mutesize];
//        dfs(nums,0);
//        return muteRet;
//    }
//
//    private void dfs(int[] nums,int pos){
//        if(pos==mutesize){
//            muteRet.add(new ArrayList<>(mutePath));
//            return;
//        }
//
//        for(int i=0;i<mutesize;i++){
//            if (!vis[i]){
//                vis[i] = true;
//                mutePath.add(nums[i]);
//                dfs(nums,pos+1);
//                vis[i] = false;
//                mutePath.removeLast();
//            }
//        }
//
//    }

//    // 子集
//
//    private int subSize;
//    private List<List<Integer>> ret = new ArrayList<>();
//    private List<Integer> path = new ArrayList<>();
//    public List<List<Integer>> subsets(int[] nums){
//        subSize = nums.length;
//        dfs(nums,0);
//        return ret;
//    }
//    private void dfs(int[] nums,int pos){
//        if(pos==nums.length){
//            ret.add(new ArrayList<>(path));
//            return;
//        }
//        path.add(nums[pos]);
//        dfs(nums,pos+1);
//        path.remove(path.size()-1);
//        dfs(nums,pos+1);
//    }

    // 组合总和
//    private List<List<Integer>> ret = new ArrayList<>();
//    private List<Integer> path = new ArrayList<>();
//    private int size;
//
//    public List<List<Integer>> combinationSum(int[] candidates, int target) {
//        size = candidates.length;
//        dfs(candidates,0,target,0);
//        return ret;
//    }
//
//    public void dfs(int[] condidates,int cur,int target,int pos){
//        if (cur==target){
//            ret.add(new ArrayList<>(path));
//            return;
//        }
//        if(cur>target) return;
//        for(int i=pos;i<size;i++){
//            cur+=condidates[i];
//            path.add(condidates[i]);
//            dfs(condidates,cur,target,i);
//            path.remove(path.size()-1);
//            cur-=condidates[i];
//
//        }
//    }


//    int m;
//    int n;
//    boolean[][] vis;
//    int[] dx = {0,0,1,-1};
//    int[] dy = {1,-1,0,0};
//    char[] word;
//    public boolean exist(char[][] board, String _word) {
//        m = board.length;
//        n = board[0].length;
//        vis = new boolean[m][n];
//        word = _word.toCharArray();
//        for (int i=0;i<m;i++){
//            for (int j=0;j<n;j++){
//                if(!vis[i][j]&&board[i][j]==word[0]){
//                    vis[i][j]=true;
//                    if(dfs(board,i,j,1)) return true;
//                    vis[i][j] = false;
//                }
//            }
//        }
//        return  false;
//    }
//
//    public boolean dfs(char[][] board,int i,int j,int pos){
//        for(int k=0;k<4;k++){
//            int x = i+dx[k];
//            int y = j+dy[k];
//            if(x>=0&&x<m&&y>=0&&y<n&&!vis[x][y]&&board[x][y]==word[pos]){
//                vis[x][y] = true;
//                if(dfs(board,x,y,pos+1)) return true;
//                vis[x][y]=false;
//            }
//        }
//        return false;
//    }


//    // 划分字母区间
//    public List<Integer> partitionLabels(String _s) {
//        int[] hash = new int[128];
//        char[] s = _s.toCharArray();
//        for(int i=0;i<s.length;i++){
//            hash[s[i]] = i;
//        }
//        int end = 0;
//        List<Integer> ret = new ArrayList<>();
//        int begin = 0;
//        for(int i=0;i<s.length;i++){
//            end = Math.max(end,hash[s[i]]);
//            if(end==i){
//                ret.add(end-begin+1);
//                begin = i+1;
//            }
//        }
//        return ret;
//    }

    // 完全平方数(完全背包问题)

    public int numSquares(int n) {
        int a = (int) Math.sqrt(n);
        boolean
        return 0;

    }

    public void IPCompare(String[] IPS){
        Arrays.sort(IPS,(ip1,ip2)->{
            String[] par1 = ip1.split("\\.");
            String[] par2 = ip2.split("\\.");
            for (int i=0;i<4;i++){
                int num1 = Integer.parseInt(par1[i]);
                int num2 = Integer.parseInt(par2[i]);
                if (num1 != num2) {
                    return num1 - num2;
                }
            }
            return 0;
        });
    }



}
